//
// Created by francklinson on 2021/7/31 AT 9:57.
//
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>
#include <functional>
#include <map>

using namespace std;

/**
 * 987. 二叉树的垂序遍历
    给你二叉树的根结点 root ，请你设计算法计算二叉树的 垂序遍历 序列。
    对位于(row, col)的每个结点而言，其左右子结点分别位于(row + 1, col - 1)和(row + 1, col + 1) 。树的根结点位于 (0, 0) 。
    二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，则按结点的值从小到大进行排序。
    返回二叉树的 垂序遍历 序列。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/vertical-order-traversal-of-a-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @return
 */

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    /**
     * 遍历树，得到每个节点的坐标信息
     * 自定义排序 按照列 行 值 的顺序进行
     * @param root
     * @return
     */
    vector<vector<int>> verticalTraversal(TreeNode *root) {
        vector<tuple<int, int, int>> nodes;
        function<void(TreeNode *, int, int)> dfs = [&](TreeNode *node, int row, int col) {
            if (!node) return;
            nodes.emplace_back(col, row, node->val);
            dfs(node->left, row + 1, col - 1);
            dfs(node->right, row + 1, col + 1);
        };
        dfs(root, 0, 0);
        sort(nodes.begin(), nodes.end());
        vector<vector<int>> ans;
        int lastCol = INT_MAX;
        for (const auto &[col,row,val]:nodes) {
            if (col != lastCol) {
                lastCol = col;
                ans.emplace_back();
            }
            ans.back().push_back(val);
        }
        return ans;
    }
};

class Solution2 { // 基于优先队列实现
public:
    struct Node {
        int x, y, val;

        Node() {}

        Node(int a, int b, int c) : x(a), y(b), val(c) {}

        // 重载比较运算符
        bool operator<(Node node) const {
            if (y != node.y) return y > node.y;
            else if (x != node.x) return x > node.x;
            return val > node.val;
        }
    };

    map<int, priority_queue<Node> > ss; // 每个列定义优先队列
    vector<vector<int>> ans;

    void dfs(int x, int y, TreeNode *root) {
        if (!root) return;
        ss[y].push({x, y, root->val}); // 放入对应列的优先队列
        dfs(x + 1, y - 1, root->left);
        dfs(x + 1, y + 1, root->right);
    }

    vector<vector<int>> verticalTraversal(TreeNode *root) {
        if (!root) return ans;
        dfs(0, 0, root);
        for (auto &[x,y] : ss) {
            ans.emplace_back();// 加一列
            while (!y.empty()) {
                ans.back().push_back(y.top().val);
                y.pop();
            }
        }
        return ans;
    }
};


int main() {
    auto n1 = TreeNode(1), n2 = TreeNode(2), n3 = TreeNode(3),
            n4 = TreeNode(4), n5 = TreeNode(5), n6 = TreeNode(6), n7 = TreeNode(7);
    n1.left = &n2;
    n1.right = &n3;
    n2.left = &n4;
    n2.right = &n5;
    n3.left = &n6;
    n3.right = &n7;
    Solution solution;
    auto ans = solution.verticalTraversal(&n1);
    for (auto &x:ans) {
        for (auto &y:x) {
            cout << y;
            cout << " ";
        }
        cout << endl;
    }
    return 0;
}

